#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
//int ret,sum,_target;
//void dfs(vector<int>& nums,int pos)
//{
//	if (pos == nums.size())
//	{
//		if (sum == _target)
//			ret++;
//		return;
//	}
//	
//		sum += nums[pos];
//		dfs(nums, pos + 1);
//		sum -= nums[pos];
//
//		sum -= nums[pos];
//		dfs(nums, pos + 1);
//		sum += nums[pos];
//}
//int findTargetSumWays(vector<int>& nums, int target) {
//	dfs(nums, 0);
//	return ret;
//}
//vector<vector<int>> ret;
//vector<int> path;
//int _target;
//void dfs(vector<int>& candidates, int sum,int pos)
//{
//	if (sum == _target)
//	{
//		ret.push_back(path);
//		return;
//	}
//	if (sum > _target) return;
//	for (int i = pos; i < candidates.size(); i++)
//	{
//		path.push_back(candidates[i]);
//		dfs(candidates, sum + candidates[i], i);
//		path.pop_back();
//	}
//}
//vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//	_target = target;
//	dfs(candidates, 0, 0);
//	return ret;
//}
//vector<string> ret;
//string path;
//char change(char ch)
//{
//	if (ch >= 'a' && ch <= 'z')
//		ch -= 32;
//	else
//		ch += 32;
//	return ch;
//}
//void dfs(string& s,int pos)
//{
//	if (pos == s.size())
//	{
//		ret.push_back(path);
//		return;
//	}
//	path.push_back(s[pos]);
//	dfs(s, pos + 1);
//	path.pop_back();
//	if (s[pos] <= '0' || s[pos] >= '9')
//	{
//		char ch = change(s[pos]);
//		path.push_back(ch);
//		dfs(s, pos + 1);
//		path.pop_back();
//	}
//}
//vector<string> letterCasePermutation(string s) {
//	dfs(s, 0);
//	return ret;
//}

//int ret, _n;
//vector<bool> check;
//void dfs(int pos) 
//{
//    if (pos == _n + 1) {
//        ret++;
//        return;
//    }
//    for (int i = 1; i <= _n; i++) {
//        if ((i % pos == 0 || pos % i == 0) && check[i] == false) {
//            check[i] = true;
//            dfs(pos + 1);
//            check[i] = false;
//        }
//    }
//}
//int countArrangement(int n) {
//    _n = n;
//    check.resize(n + 1, false);
//    dfs(1);
//    return ret;
//}
vector<vector<string>> ret;
vector<string> path;
int _n;
vector<bool> checkcol;
vector<bool> checkdiag1, checkdiag2;
void dfs(int pos)
{
	if (pos == _n)
	{
		ret.push_back(path);
		return;
	}
	for (int i = 0; i < _n; i++)
	{
		if (checkcol[i] == false && checkdiag1[pos - i + _n] == false
			&& checkdiag2[pos + i] == false)
		{
			path[pos][i] = 'Q';
			checkcol[i] == true;
			checkdiag1[pos - i + _n] == true;
			checkdiag2[pos + i] == true;

			dfs(pos + 1);
			path[pos][i] = '.';
			checkcol[i] == false;
			checkdiag1[pos - i + _n] == false;
			checkdiag2[pos + i] == false;
		}
	}
}
vector<vector<string>> solveNQueens(int n) {
	_n = n;
	path.resize(n);
	for (int i = 0; i < n; i++)
		path[i].resize(n, '.');
	checkcol.resize(n, false);
	checkdiag1.resize(2 * n, false);
	checkdiag2.resize(2 * n, false);
	dfs(0);
	return ret;
}
int main()
{

	return 0;
}